#include<iostream>


class AVLTree{
    public:
    AVLTree();
    ~AVLTree();
    AVLTree( const AVLTree &rhs);
    AVLTree( AVLTree && rhs);

    const int & findMax() const;
    const int & findMin() const;

    bool contains( const int &x) const;
    bool isEmpty() const;

    void makeEmpty();
    void insert( const int &x);
    void insert( int && x);

    void remove(const int &x);
    AVLTree & operator=(const AVLTree &rhs);
    AVLTree & operator=(AVLTree && rhs);

    private:
    struct AVLNode{
        int element;
        AVLNode* left;
        AVLNode* right;

        int height;

        AVLNode(const int &ele, AVLNode *lt, AVLNode *rt, int h=0)
        : element{ele}, left{lt}, right{rt}, height{h} {}
        AVLNode(int &&ele, AVLNode *lt, AVLNode *rt, int h=0)
        :element{std::move(ele)}, left{lt}, right{rt}, height{h} {}

    }; 
    int height(AVLNode* t) const{
        return t == nullptr ? -1: t->height;
    }
    //左单旋
    void rotateWithLeftChild(AVLNode *& k2){
        AVLNode* tmp1 = k2->left;
        k2->left = tmp1->right;
        tmp1->right = k2;

        k2->height = std::max(height(k2->right), height(k2->left)) + 1;
        tmp1->height = std::max(height(tmp1->right), height(tmp1->left)) +1;

        k2 = tmp1;
    }
    //右单旋
    void rotateWithRightChild(AVLNode *& k2){
        AVLNode* tmp1 = k2->right;
        k2->right = tmp1->left;
        tmp1->left = k2;

        k2->height = std::max(height(k2->right), height(k2->left)) + 1;
        tmp1->height = std::max(height(tmp1->right), height(tmp1->left)) +1;

        k2 = tmp1;
    }

    //双旋 LR
    void doubleRotateLR(AVLNode *& k3){
        rotateWithRightChild(k3->left);
        rotateWithLeftChild(k3);

    }
    //双旋 RL
    void doubleRotateRL(AVLNode *& k4){
        rotateWithLeftChild(k4->right);
        rotateWithRightChild(k4);
    }

    static const int ALLOWED_IMBALANCE = 1;

    void balance(AVLNode *&t){
        if(t == nullptr){
            return ;
        }
        if(height(t->left) - height(t->right) > ALLOWED_IMBALANCE)
            if(height(t->left->left) - height(t->left->right) > ALLOWED_IMBALANCE)
                rotateWithLeftChild(t);//LL型
            else
                doubleRotateLR(t); //LR型

        else if(height(t->right) - height(t->left) > ALLOWED_IMBALANCE)
            if(height(t->right->right) - height(t->right->left) > ALLOWED_IMBALANCE)
                rotateWithRightChild(t); //RR
            else
                doubleRotateRL(t); //RL

        t->height = std::max(height(t->left), height(t->right)) + 1;
    }





};

